package com.wdc.binarytree;

/**
 * leetcode 1008 根据BST的前序遍历，构造一棵二叉树
 * 分而治之的思路
 */
public class E08Leetcode1008 {

    public TreeNode bstFromPreorder(int[] preorder) {

       return partition(preorder,0,preorder.length - 1);

    }

    private TreeNode partition(int[] preorder,int start,int end) {
        //传入的依次递归,先判断传入的start 是否小于 end，
        if (start > end){
            return null;
        }
        //如果不为空则找出其根结点，以及左右子树的分界线
        TreeNode root = new TreeNode(preorder[start]);
        int index = start + 1;
        while(index <= end){
            if (preorder[index] > preorder[start]){
                break;
            }
            index++;
        }
        //找到了分界线,则开始递归分配其左右子树
        root.left = partition(preorder,start +1 ,index - 1);
        root.right = partition(preorder,index,end);

        return root;
    }

}
